// https://leetcode-cn.com/problems/reconstruct-itinerary/
// 332. 重新安排行程

import java.util.*;

class Solution {
    private Deque<String> res;
    private Map<String, Map<String, Integer>> map;

    public List<String> findItinerary(List<List<String>> tickets) {
        map = new HashMap<>();
        res = new LinkedList<>();

        for (List<String> t : tickets) {
            Map<String, Integer> temp;
            if (map.containsKey(t.get(0))) {
                temp = map.get(t.get(0));
                temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
            } else {
                temp = new TreeMap<>();
                temp.put(t.get(1), 1);
            }
            map.put(t.get(0), temp);
        }

        res.add("JFK");
        BackTrack(tickets.size());
        return new ArrayList<>(res);
    }

    private boolean BackTrack(int ticket_num) {
        if (res.size() == ticket_num + 1) {
            return true;
        }

        String last = res.getLast();
        if (map.containsKey(last)) {
            for (Map.Entry<String, Integer> target : map.get(last).entrySet()) {
                
                int count = target.getValue();
                if (count > 0) {
                    res.add(target.getKey());
                    target.setValue(count - 1);
                    if (BackTrack(ticket_num)) {
                        return true;
                    }
                    target.setValue(count);
                    res.removeLast();
                }
            }
        }
        return false;
    }
}
